Introduction to DSA
Data Structures and Algorithms (DSA) are crucial for solving complex computational problems. Understanding DSA concepts improves coding efficiency and enhances your ability to optimize solutions. It forms the backbone of efficient coding and problem-solving in competitive programming and software development.
Arrays
An array is a collection of items stored at contiguous memory locations. Arrays allow random access to elements, and are useful in sorting and searching algorithms.
Arrays offer fast access to elements via index, making them ideal for read-heavy operations like searching, sorting, and iteration.
Arrays have fixed sizes, making dynamic allocation and deletion difficult. They also consume more memory if not optimized.
int arr[] = {1, 2, 3, 4, 5};
for(int i = 0; i < 5; i++) {
printf("%d", arr[i]);
}
Linked List
A linked list is a linear data structure where each element (node) points to the next, allowing for dynamic memory allocation.
Linked lists provide efficient insertion and deletion compared to arrays, especially when the size of the data structure is unknown beforehand.
Accessing elements in a linked list requires traversing from the head, making random access less efficient.
struct Node {
int data;
struct Node* next;
};
struct Node* head = NULL;
Stack
A stack is a linear data structure that follows the Last In First Out (LIFO) principle. Common operations include push (insertion) and pop (removal).
Stacks are excellent for recursive algorithms and can be used to solve problems like balancing parentheses and evaluating expressions.
Stacks are limited in terms of size, especially when implemented using arrays, as they cannot dynamically expand.
int stack[MAX];
int top = -1;
void push(int data) {
stack[++top] = data;
}
Queue
A queue is a linear data structure that follows the First In First Out (FIFO) principle. It is used in scheduling and task management algorithms.
Queues provide efficient insertion and deletion of elements, making them ideal for applications like task scheduling, BFS, and resource allocation.
Queues can become inefficient when implemented using arrays, as shifting elements may be necessary.
int queue[MAX];
int front = -1, rear = -1;
void enqueue(int data) {
queue[++rear] = data;
}
Tree
A tree is a hierarchical data structure consisting of nodes, where each node contains a value and references to its child nodes.
Trees offer efficient search, insertion, and deletion, making them suitable for databases, file systems, and network structures.
Trees can become unbalanced, leading to inefficient operations in the worst-case scenarios.
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};
Graph
A graph is a data structure that consists of vertices (nodes) and edges (connections), representing relationships between entities.
Graphs are ideal for representing networks, such as social connections, transportation routes, and communication pathways.
Graphs can be memory-intensive due to the storage of all vertices and edges, especially in dense graphs.
struct Graph {
int numVertices;
int** adjMatrix;
};